package org.example;

import java.util.*;

public class AppTest05 {
    // nim game 1 2 3
    class Solution {
        public boolean canWinNim(int n) {
            return n % 4 != 0;
        }
    }

    // Range Sum Query 2
    class NumArray {
        int[] sum;
        public NumArray(int[] nums) {
            sum = new int[nums.length + 1];
            for (int i = 0; i < nums.length; i++) {
                sum[i + 1] = sum[i] + nums[i];
            }
        }

        public int sumRange(int left, int right) {
            return sum[right + 1] - sum[left];
        }
    }
    // Range Sum Query 3
    class NumArray {
        int[] sum;
        public NumArray(int[] nums) {
            sum = new int[nums.length + 1];
            for (int i = 0; i < nums.length; i++) {
                sum[i + 1] = sum[i] + nums[i];
            }
        }

        public int sumRange(int left, int right) {
            return sum[right + 1] - sum[left];
        }
    }

    // Power of 3
    class Solution {
        // 1
        public boolean isPowerOfThree(int n) {
            double tmp = Math.log(Integer.MAX_VALUE) / Math.log(3);
            int tmp2 = (int) tmp;
            int tmp3 = (int) Math.pow(3, tmp2);
            System.out.println(tmp3);
            return n > 0 && tmp % n == 0;
        }
        // 2
        public boolean isPowerOfThree(int n) {
            double index1 = Math.log(Integer.MAX_VALUE) / Math.log(3);
            int index2 = (int) index1;
            int pow1 = (int) Math.pow(3, index2);
            return n > 0 && pow1 % n == 0;
        }
        // 3
        public boolean isPowerOfThree(int n) {
            double v1 = Math.log(Integer.MAX_VALUE) / Math.log(3);
            int v2 = (int) v1;
            int v3 = (int) Math.pow(3, v2);
            return n > 0 && v3 % n == 0;
        }
    }

    // Power of 4
    class Solution {
        // 1
        public boolean isPowerOfFour(int n) {
            return n > 0 && (Math.log(n) / Math.log(2)) % 2 == 0;
        }

        //2
        public boolean isPowerOfFour(int n) {
            return n > 0 && (Math.log(n) / Math.log(2)) % 2 == 0;
        }

        // 3
        public boolean isPowerOfFour(int n) {
            return n > 0 && (Math.log(n) / Math.log(2) %2 == 0);
        }
    }

    // Reverse String
    class Solution {
        // 1
        public void reverseString(char[] s) {
            int left = 0, right = s.length - 1;
            while (left < right) {
                char tmp = s[left];
                s[left] = s[right];
                s[right] = tmp;
                left++;
                right--;
            }
        }
        // 2
        public void reverseString(char[] s) {
            int left = 0, right = s.length - 1;
            while (left < right) {
                char tmp = s[left];
                s[left++] = s[right];
                s[right--] = tmp;
            }
        }
        // 3
        public void reverseString(char[] s) {
            int left = 0, right = s.length - 1;
            while (left < right) {
                char tmp = s[left];
                s[left] = s[right];
                s[right] = tmp;
            }
        }
    }

    // 349 Intersection of two arrays 1
    class Solution {
        public int[] set_interseciton(HashSet<Integer> set1, HashSet<Integer> set2) {
            int[] output = new int[set1.size()];
            int idx = 0;
            for (Integer s : set1) {
                if (set2.contains(s)) {
                    output[idx] = s;
                    idx++;
                }
            }
            return Arrays.copyOf(output, idx);
        }

        public int[] intersection(int[] nums1, int[] nums2) {
            HashSet<Integer> set1 = new HashSet<>();
            for (Integer n : nums1) set1.add(n);
            HashSet<Integer> set2 = new HashSet<>();
            for (Integer n : nums2) set2.add(n);

            if (set1.size() < set2.size()) {
                return set_interseciton(set1, set2);
            } else {
                return set_interseciton(set2, set1);
            }
        }
    }
    // 349 Intersection of two arrays 2
    class Solution {
        public int[] set_intersection(HashSet<Integer> set1, HashSet<Integer> set2) {
            int [] res = new int[set1.size()];
            int idx = 0;
            for (int num : set1) {
                if (set2.contains(num)) {
                    res[idx++] = num;
                }
            }
            return Arrays.copyOf(res, idx);
        }

        public int[] intersection(int[] nums1, int[] nums2) {
            HashSet<Integer> set1 = new HashSet<>();
            for (int num: nums1) {
                set1.add(num);
            }
            HashSet<Integer> set2 = new HashSet<>();
            for (int num: nums2) {
                set2.add(num);
            }
            if (set1.size() < set2.size()) {
                return set_intersection(set1, set2);
            } else {
                return set_intersection(set2, set1);
            }
        }
    }
    // 349 Intersection of two arrays 3
    class Solution {
        public int[] set_intersection(HashSet<Integer> set1, HashSet<Integer> set2) {
            int[] res = new int[set1.size()];
            int idx = 0;
            for (int num : set1) {
                if (set2.contains(num)) {
                    res[idx++] = num;
                }
            }
            return Arrays.copyOf(res, idx);
        }

        public int[] intersection(int[] nums1, int[] nums2) {
            HashSet<Integer> set1 = new HashSet<>();
            for (int num : nums1) {
                set1.add(num);
            }
            HashSet<Integer> set2 = new HashSet<>();
            for (int num : nums2) {
                set2.add(num);
            }
            if (set1.size() < set2.size()) return set_intersection(set1, set2);
            else return set_intersection(set2, set1);
        }
    }

    // 374 Guess Number Higher or Lower
    public class Solution extends GuessGame {
        // 1
        public int guessNumber(int n) {
            int low = 1, high = n;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                int res = guess(mid);
                if (res == 0) return mid;
                if (res < 0) high = mid - 1;
                if (res > 0) low = mid + 1;
            }
            return -1;
        }
        // 2
        public int guessNumber(int n) {
            int left = 1, right = n;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (guess(mid) == 0) return mid;
                if (guess(mid) < 0) right = mid - 1;
                if (guess(mid) > 0) left = mid + 1;
            }
            return -1;
        }
        // 3
        public int guessNumber(int n) {
            int left = 1, right = n;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (guess(mid) == 0) return mid;
                if (guess(mid) < 0) right = mid - 1;
                else left = mid + 1;
            }
            return -1;
        }
    }

    // 387 First Unique Character in a String
    class Solution {
        // 1
        public int firstUniqChar(String s) {
            HashMap<Character, Integer> count = new HashMap<>();
            int n = s.length();
            for (int i = 0; i < n; i++) {
                char c = s.charAt(i);
                count.put(c, count.getOrDefault(c, 0) + 1);
            }
            for (int i = 0; i < n; i++) {
                if (count.get(s.charAt(i)) == 1) return i;
            }
            return -1;
        }
        // 2
        public int firstUniqChar(String s) {
            HashMap<Character, Integer> charTimes = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                charTimes.put(s.charAt(i), charTimes.getOrDefault(s.charAt(i), 0) + 1);
            }
            for (int i = 0; i < s.length(); i++) {
                if (charTimes.get(s.charAt(i)) == 1) return i;
            }
            return -1;
        }
        // 3
        public int firstUniqChar(String s) {
            HashMap<Character, Integer> charTimes = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                charTimes.put(s.charAt(i), charTimes.getOrDefault(s.charAt(i), 0) + 1);
            }
            for (int i = 0; i < s.length(); i++) {
                if (charTimes.get(s.charAt(i)) == 1) {
                    return i;
                }
            }
            return -1;
        }
    }

    // 409 Longest Palindrome
    class Solution {
        // 1
        public int longestPalindrome(String s) {
            int[] count = new int[128];
            for (char c : s.toCharArray()) {
                count[c]++;
            }
            int ans = 0;
            for (int v : count) {
                ans += v / 2 * 2;
                if (v % 2 == 1 && ans % 2 == 0) {
                    ans++;
                }
            }
            return ans;
        }
        // 2
        public int longestPalindrome(String s) {
            int[] tmp = new int[128];
            for (int i = 0; i < s.length(); i++) {
                int sChar = s.charAt(i);
                tmp[sChar]++;
            }
            int res = 0;
            for (int num : tmp){
                res += num / 2 * 2;
                if(res % 2 == 0 && num % 2 == 1){
                    res++;
                }
            }
            return res;
        }
        // 3
        public int longestPalindrome(String s) {
            int[] tmp = new int[128];
            for (int i = 0; i < s.length(); i++) {
                tmp[s.charAt(i)]++;
            }
            int res = 0;
            for (int num : tmp) {
                res += num / 2 * 2;
                if (num % 2 == 1 && res % 2 == 0) {
                    res++;
                }
            }
            return res;
        }
    }

    // 412 FizzBuzz
    class Solution {
        // 1
        public List<String> fizzBuzz(int n) {
            List<String> ans = new ArrayList<>();
            HashMap<Integer, String> fizzBizzDict= new HashMap<>(){
                {
                    put(3, "Fizz");
                    put(5, "Buzz");
                }
            };
            for (int num = 1; num <= n; num++) {
                String numAnsStr = "";
                for (Integer key : fizzBizzDict.keySet()){
                    if (num % key == 0) {
                        numAnsStr += fizzBizzDict.get(key);
                    }
                }
                if (numAnsStr.equals("")) {
                    numAnsStr += Integer.toString(num);
                }
                ans.add(numAnsStr);
            }
            return ans;
        }
        // 2
        public List<String> fizzBuzz(int n) {
            List<String> ans = new LinkedList<>();
            HashMap<Integer, String> gameMap = new HashMap<>(){
                {
                    put(3, "Fizz");
                    put(5, "Buzz");
                }
            };
            String ansString = "";
            for (int i = 1; i <- n; i++) {
                // todo 遍历key的值
                for (int key : gameMap.keySet()) {
                    if (i % key == 0) {
                        ansString += gameMap.get(key);
                    }
                }
                // todo 利用判空做条件，放在循环体外面。
                if (ansString.equals("")) {
                    ansString = Integer.toString(i);
                }
                ans.add(ansString);
            }
            return ans;
        }
        // 3
        public List<String> fizzBuzz(int n) {
            List<String> ans = new ArrayList<>();
            HashMap<Integer, String> gameMap = new HashMap<>() {
                {
                    put(3, "Fizz");
                    put(5, "Buzz");
                }
            };
            for (int i = 1; i <= n; i++) {
                String ansString = "";
                for (Integer key : gameMap.keySet()) {
                    if (i % key == 0) {
                        ansString += gameMap.get(key);
                    }
                }
                if (ansString.equals("")) {
                    ansString += Integer.toString(i);
                }
                ans.add(ansString.toString());
            }
            return ans;
        }
    }

    // 415 Add Strings
    class Solution {
        // 1
        public String addStrings(String num1, String num2){
            StringBuilder ans = new StringBuilder();
            int carry = 0;
            int p1 = num1.length() - 1;
            int p2 = num2.length() - 1;
            while (p1 >= 0 || p2 >= 0) {
                int x1 = p1 >= 0 ? num1.charAt(p1) - '0' : 0;
                int x2 = p2 >= 0 ? num2.charAt(p2) - '0' : 0;
                int value = (x1 + x2 + carry) % 10;
                carry = (x1 + x2 + carry) / 10;
                ans.append(value);
                p1--;
                p2--;
            }
            if (carry == 1) ans.append(carry);
            return ans.reverse().toString();
        }
        // 2
        public String addStrings(String num1, String num2){
            int p1 = num1.length() - 1, p2 = num2.length() - 1;
            StringBuilder ans = new StringBuilder();
            int carry = 0, sumX1X2 = 0;
            while (p1 >= 0 || p2 >= 0) {
                int x1 = p1 >= 0 ? num1.charAt(p1) - '0' : 0;
                int x2 = p2 >= 0 ? num2.charAt(p2) - '0' : 0;
                sumX1X2 = (x1 + x2 + carry) % 10;
                carry = (x1 + x2 + carry) / 10;
                ans.append(sumX1X2);
                p1--;
                p2--;
            }
            if (carry == 1) ans.append(carry);
            return ans.reverse().toString();
        }
        // 3
        public String addStrings(String num1, String num2){
            int p1 = num1.length() - 1, p2 = num2.length() - 1;
            int carry = 0, ansChar = 0;
            StringBuilder ans = new StringBuilder();
            while (p1 >= 0 || p2 >= 0) {
                int x1 = p1 >= 0 ? num1.charAt(p1) - '0': 0;
                int x2 = p2 >= 0 ? num2.charAt(p2) - '0': 0;
                ansChar = (x1 + x2 + carry) % 10;
                carry = (x1 + x2 + carry) / 10;
                ans.append(ansChar);
                p1--;
                p2--;
            }
            if (carry == 1) ans.append(carry);
            return ans.reverse().toString();
        }
    }

    // 434 Number of Segments in a String
    class Solution {
        // 1
        public int countSegments(String s) {
            int segmentCount = 0;
            for (int i = 0; i < s.length(); i++) {
                if ( (i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != ' ') segmentCount++;
            }
            return segmentCount;
        }
        // 2
        public int countSegments(String s) {
            int ans = 0;
            for (int i = 0; i < s.length(); i++) {
                if((i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != ' ') {
                    ans++;
                }
            }
            return ans;
        }
        // 3
        public int countSegments(String s) {
            int ans = 0;
            for (int i = 0; i < s.length(); i++) {
                if ((i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != ' ') ans++;
            }
            return ans;
        }
    }

    // 441 Arranging Coins
    class Solution {
        // 1
        public int arrangeCoins(int n) {
            return (int) (Math.sqrt(2 * n + 0.25) - 0.5);
            return (int) (Math.sqrt(2 * (long) n + 0.25) - 0.5);
        }
        // 2
        public int arrangeCoins(int n) {
            return (int) (Math.sqrt(2 * (long) n + 0.25) - 0.5);
        }
        // 3
        public int arrangeCoins(int n) {
            return (int) (Math.sqrt(2 * (long) n + 0.25) - 0.5);
        }
    }

    // 507 Perfect Number
    class Solution {
        // 1
        public boolean checkPerfectNumber(int num) {
            if (num <= 0) return false;
            int sum = 0;
            for (int i = 1; i * i <= num ; i++) {
                if (num % i == 0) {
                    sum += i;
                    if ( i * i != num) sum += num / i;
                }
            }
            return num == sum - num;
        }
        // 2
        public boolean checkPerfectNumber(int num) {
            if (num <= 0) return false;
            int ans = 0;
            for (int i = 1; i * i < num ; i++) {
                if (num % i == 0) {
                    ans += i;
                    if ( i * i != num) {
                        ans += num / i;
                    }
                }
            }
            return num == ans - num;
        }
        // 3
        public boolean checkPerfectNumber(int num) {
            int sum = 0;
            for (int i = 1; i * i <= num; i++) {
                if (num % i == 0) {
                    sum += i;
                    if (i * i != num) {
                        sum += num / i;
                    }
                }
            }
            return sum == 2 * num;
        }
    }

    // 509 Fib
    class Solution {
        // 1
        public int fib(int n) {
            if (n < 2) return n;
            int p = 0, q = 0, r = 1;
            for (int i = 2; i <= n ; i++) {
                p = q;
                q = r;
                r = p + q;
            }
            return r;
        }
        // 2
        public int fib(int n) {
            if (n < 2) return n;
            int p = 0, q = 0, r = 1;
            for (int i = 2; i <= n ; i++) {
                p = q;
                q = r;
                r = p + q;
            }
            return r;
        }
        // 3
        public int fib(int n) {
            // todo 边界条件
            if (n < 2) return n;
            int p = 0, q = 0, r = 1;
            for (int i = 2; i <= n; i++) {
                p = q;
                q = r;
                r = p + q;
            }
            return r;
        }
    }

    // 520 Detect Capital
    class Solution {
        // 1
        public boolean detectCapitalUse(String word) {
            return word.matches("[A-Z]*|.[a-z]*");
        }
        // 2
        public boolean detectCapitalUse(String word) {
            return word.matches("[A-Z]*|.[a-z]*");
        }
        // 3
        public boolean detectCapitalUse(String word) {
            return word.matches("[A-Z]*|.[a-z]*");
        }
    }

    // 521 最长特殊序列
    class Solution {
        // 1
        public int findLUSlength(String a, String b) {
            if (a.equals(b)) return -1;
            return Math.max(a.length(), b.length());
        }
        // 2
        public int findLUSlength(String a, String b) {
            if (a.equals(b)) return -1;
            return Math.max(a.length(), b.length());
        }
        // 3
        public int findLUSlength(String a, String b) {
            if (a.equals(b)) return -1;
            return Math.max(a.length(),b.length());
        }
    }

    // 541 Reverse String II
    class Solution {
        // 1
        public String reverseStr(String s, int k) {
            char[] a = s.toCharArray();
            for (int start = 0; start < a.length; start += 2 * k) {
                int i = start, j = Math.min(start + k - 1, a.length - 1);
                while (i < j) {
                    char tmp = a[i];
                    a[i++] = a[j];
                    a[j--] = tmp;
                }
            }
            return new String(a);
        }
        // 2
        public String reverseStr(String s, int k) {
            char[] charS = s.toCharArray();
            for (int start = 0; start < charS.length; start += 2 * k) {
                // todo 注意length-1
                int left = start, right = Math.min(charS.length - 1, start + k - 1);
                while (left < right) {
                    char tmp = charS[left];
                    // todo 注意递增递减
                    charS[left++] = charS[right];
                    charS[right--] = tmp;
                }
            }
            return new String(charS);
        }
        // 3
        public String reverseStr(String s, int k) {
            char[] a = s.toCharArray();
            for (int start = 0; start < a.length; start += 2 * k) {
                int left = start, right = Math.min(start + k - 1, a.length - 1);
                while (left < right) {
                    char tmp = a[left];
                    a[left++] = a[right];
                    a[right--] = tmp;
                }
            }
            return new String(a);
        }
    }

    // 557 Reverse Words in a String
    class Solution {
        // 1
        public String reverseWords(String s) {
            String[] words = s.split(" ");
            StringBuilder res = new StringBuilder();
            for (String word : words) {
                res.append(new StringBuilder(word).reverse().toString() + " ");
            }
            return res.toString().trim();
        }
        // 2
        public String reverseWords(String s) {
            String[] words = s.split(" ");
            StringBuilder res = new StringBuilder();
            for (String word : words) {
                res.append(new StringBuilder(word).reverse().append(" "));
            }
            return res.toString().trim();
        }
        // 3
        public String reverseWords(String s) {
            String[] words = s.split(" ");
            StringBuilder res = new StringBuilder();
            for (String word : words) {
                res.append(new StringBuilder(word).reverse().append(" "));
            }
            return res.toString().trim();
        }
    }

    // 563 Binary Tree Tilt
    // 1
    class Solution {
        private int totalTilt = 0;

        protected int valueSum(TreeNode node) {
            if (node == null) return 0;
            // 形成循环
            int leftSum = this.valueSum(node.left);
            int rightSum = this.valueSum(node.right);
            int tilt = Math.abs(leftSum - rightSum);
            this.totalTilt += tilt;
            return node.val + leftSum + rightSum;
        }

        public int findTilt(TreeNode root){
            this.valueSum(root);
            return this.totalTilt;
        }
    }
    // 2
    class Solution {
        int totalTilt = 0;
        public int valueSum(TreeNode node) {
            // todo 边界条件
            if (node == null) return 0;

            int left = valueSum(node.left);
            int right = valueSum(node.right);
            int tilt = Math.abs(left - right);
            totalTilt += tilt;
            return node.val + left + right;
        }

        public int findTilt(TreeNode root){
            valueSum(root);
            return totalTilt;
        }
    }
    // 3
    class Solution {
        int totalTilt = 0;

        public int getSum(TreeNode node) {
            if (node == null) return 0;
            int left = getSum(node.left);
            int right = getSum(node.right);
            int tilt = Math.abs(left - right);
            totalTilt += tilt;
            return node.val + left + right;
        }

        public int findTilt(TreeNode root){
            getSum(root);
            return this.totalTilt;
        }
    }

    // 566 重塑矩阵
    class Solution {
        // 1
        public int[][] matrixReshape(int[][] mat, int r, int c) {
            int m = mat.length, n = mat[0].length;
            if (m * n != r * c) return mat;
            int[][] ans = new int[r][c];
            for (int i = 0; i < m * n; i++){
                ans[i / c][i % c] = mat[i / n] [i % n];
            }
            return ans;
        }
        // 2
        public int[][] matrixReshape(int[][] mat, int r, int c) {
            int m = mat.length, n = mat[0].length;
            if (m * n != r * c) return mat;
            int[][] res = new int[r][c];
            for (int i = 0; i < m * n; i++) {
                res[i / c][i % c] = mat[i / n][i % n];
            }
            return res;
        }
    }

    // 575 Distribute Candies
    class Solution {
        // 1
        public int distributeCandies(int[] candies) {
            HashSet<Integer> set = new HashSet<>();
            for (int candy : candies) {
                set.add(candy);
            }
            return Math.min(set.size(), candies.length / 2);
        }
    }
}
